package tree;

import java.util.ArrayList;
import java.util.Stack;

/**题目：二叉树的前序遍历
 * @Author Gavin
 * @date 2022.01.04 23:00
 */
public class tree_15 {

    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        TreeNode left=new TreeNode(2);
        TreeNode right=new TreeNode(3);
        root.left=left;
        root.right=right;
        System.out.println(solution(root));

    }
    /**
     * 第一种方法：递归
     */
    public static ArrayList<Integer> solution(TreeNode root){
        ArrayList<Integer> result=new ArrayList<>();
        rec(root,result);
        return result;
    }
    private static void rec(TreeNode root,ArrayList<Integer> list){
        if(root==null)return;
        list.add(root.val);//放在不同位置就是不同的遍历
        rec(root.left,list);
        rec(root.right,list);
    }
    //下面这种方式也可以遍历二叉树的任何方式。先序，中序，后序
    public ArrayList<Integer>  solution_4(TreeNode root){
        ArrayList<Integer> result = new ArrayList<>();
        if(root==null)return result;
        ArrayList<Integer> left=solution_4(root.left);
        ArrayList<Integer> right=solution_4(root.right);
        result.addAll(left);
        result.addAll(right);
        result.add(root.val);
        return result;
    }

    /**
     * 第二种方法：使用一个栈来处理
     */
    public ArrayList<Integer> solution_2(TreeNode root){
        ArrayList<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                result.add(root.val);
                stack.push(root);
                root=root.left;
            }
            root=stack.pop().right;//这里stack.pop出来的就是树的最后一个左节点
        }
        return result;
    }
    /**
     * 第三种方法：也是利用栈的特性,先进后出
     * 先让节点的右节点进，然后左节点进
     * 出来就是先左节点，后右节点，满足前序遍历的要求
     */
    public ArrayList<Integer> solution_3(TreeNode root){
        ArrayList<Integer> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
           TreeNode node=stack.pop();
           result.add(node.val);
           if(node.right!=null)stack.push(node.right);
           if(node.left!=null)stack.push(node.left);
        }
        return result;
    }
}
